package com.leetcode.dynamic_programming;

/**
 * @author Dennis Li
 * @date 2020/8/12 19:55
 */
public class MaxProitIV_188 {

    public int maxProfit(int k, int[] prices) {
        int days = prices.length;

        if(k > days / 2)
            return greedy(prices);

        final int[][][] dp = new int[days][k + 1][2];
        for (int i = 0; i < days; i++) {
            // 没有进行交易的时候不可能有股票
            // 注意不是Integer.MAX_VALUE，而是-prices[i] -- 这个是最初的购买价格
            dp[i][0][1] = -prices[i];
        }

        for (int i = 0; i <= k; i++) {
            dp[0][i][1] = -prices[0];
        }

        for (int i = 1; i < days; i++) {
            for (int j = 1; j <= k; j++) {
                // 买了还没有售出，不算一笔交易完成。单纯售出不算进行一次交易
                dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]);
                // 要么持有股票不买，要么买了等待售出
                dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]);
            }
        }

        return dp[days - 1][k][0];
    }

    // LeetCode 122
    private int greedy(int[] prices) {
        final int len = prices.length;
        int max = 0;
        for (int i = 1; i < len; i++) {
            if(prices[i] > prices[i - 1])
                max += prices[i] - prices[i - 1];
        }
        return max;
    }

}
